๐Ÿ’ก ๋น„ํŠธ๋งˆ์Šคํฌ(BitMask)

@Seongukbaek Posted May 16, 2022 ยท Updated May 16, 2022 ยท 8 min read

๐Ÿงท ๋น„ํŠธ๋งˆ์Šคํฌ

ํ˜„๋Œ€์˜ ๋ชจ๋“  CPU๋Š” ์ด์ง„์ˆ˜๋ฅผ ์ด์šฉํ•ด ๋ชจ๋“  ์ž๋ฃŒ๋ฅผ ํ‘œํ˜„ํ•˜๊ณ , ์ด๋Š” ์ด์ง„๋ฒ• ๊ด€๋ จ ์—ฐ์‚ฐ์„ ์•„์ฃผ ๋นจ๋ฆฌ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์žฅ์ ์ด ์žˆ๋‹ค. ์ด์™€ ๊ฐ™์€ ํŠน์„ฑ์„ ์ด์šฉํ•ด ์ •์ˆ˜์˜ ์ด์ง„์ˆ˜ ํ‘œํ˜„์„ ์ž๋ฃŒ ๊ตฌ์กฐ๋กœ ์“ฐ๋Š” ๊ธฐ๋ฒ•์„ ๋งํ•œ๋‹ค.

์ง‘ํ•ฉ์˜ ์š”์†Œ๋“ค์˜ ๊ตฌ์„ฑ ์—ฌ๋ถ€๋ฅผ ํ‘œํ˜„ํ•  ๋•Œ ์œ ์šฉํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

๐Ÿชš ์žฅ์ 

๋” ๋น ๋ฅธ ์ˆ˜ํ–‰ ์‹œ๊ฐ„

  • ๋น„ํŠธ ๋งˆ์Šคํฌ ์—ฐ์‚ฐ์€ O(1)O(1) ์— ๊ตฌํ˜„๋˜๋Š” ๊ฒƒ์ด ๋งŽ์•„ ๋‹ค๋ฅธ ์ž๋ฃŒ ๊ตฌ์กฐ๋ณด๋‹ค ํ›จ์”ฌ ๋นจ๋ฆฌ ๋™์ž‘ํ•œ๋‹ค.
  • ๋ฌผ๋ก  ๋น„ํŠธ๋งˆ์Šคํฌ๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๋ง์€ ์›์†Œ์˜ ์ˆ˜๊ฐ€ ๋งŽ์ง€ ์•Š๋‹ค๋Š” ์˜๋ฏธ์ด๋ฏ€๋กœ, ์—„์ฒญ๋‚˜๊ฒŒ ํฐ ์†๋„ ํ–ฅ์ƒ์€ ์•„๋‹ˆ๋‹ค.

๊ฐ„๊ฒฐํ•œ ์ฝ”๋“œ

  • ๋‹ค์–‘ํ•œ ์ง‘ํ•ฉ ์—ฐ์‚ฐ๋“ค์„ ๋ฐ˜๋ณต๋ฌธ ์—†์ด ํ•œ ์ค„์— ์“ธ ์ˆ˜ ์žˆ์–ด ์งง์€ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•  ์ˆ˜ ์žˆ๋‹ค.

๋” ์ž‘์€ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰

  • ๊ฐ™์€ ๋ฐ์ดํ„ฐ๋ฅผ ๋” ์ ์€ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ์ด๋กœ ์ธํ•ด ๋” ๋งŽ์€ ๋ฐ์ดํ„ฐ๋ฅผ ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ด์„œ ์ €์žฅํ•ด ๋‘˜ ์ˆ˜ ์žˆ๊ฒŒ ๋œ๋‹ค.

์—ฐ๊ด€ ๋ฐฐ์—ด์„ ๋ฐฐ์—ด๋กœ ๋Œ€์ฒด

  • ์ง‘ํ•ฉ์„ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

DP๋‚˜ ์ˆœ์—ด ๋“ฑ ๋ฐฐ์—ด ํ™œ์šฉ๋งŒ์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์—†๋Š” ๋ฌธ์ œ ํ•ด๊ฒฐ

๐Ÿชš ๋น„ํŠธ๋งˆ์Šคํ‚น ํ™œ์šฉ

0๊ณผ 1๋กœ flag ํ™œ์šฉํ•˜๊ธฐ

[1,2,3,4,5] ๋ผ๋Š” ์ง‘ํ•ฉ์ด ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ์ž„์˜๋กœ ๋ช‡ ๊ฐœ๋ฅผ ๊ณจ๋ผ ๋ฝ‘์•„ ํ™•์ธํ•ด์•ผ ํ•˜๋Š” ์ƒํ™ฉ์ด ์ฃผ์–ด์กŒ๋‹ค. (๋ถ€๋ถ„ ์ง‘ํ•ฉ์„ ์˜๋ฏธ)

{1}, {2}, ... , {1,2}, {1,2,5}, {1,2,3,4,5}

๋น„ํŠธ๋งˆ์Šคํ‚น์„ ํ†ตํ•ด, ๊ฐ ์š”์†Œ๋ฅผ ์ธ๋ฑ์Šค์ฒ˜๋Ÿผ ํ‘œํ˜„ํ•˜์—ฌ ํšจ์œจ์ ์ธ ์ ‘๊ทผ์„ ํ•  ์ˆ˜ ์žˆ๋‹ค.

[1,2,3,4,5] -> 11111 [2,3,4,5] -> 11110 [1,2,5] -> 10011 [3] -> 00100

์ด๋Ÿฌํ•œ 2์ง„์ˆ˜๋ฅผ 10์ง„์ˆ˜๋กœ ๋ณ€ํ™˜ํ•˜์—ฌ ๋ถ€๋ถ„์ง‘ํ•ฉ์„ ์ •์ˆ˜๋ฅผ ํ†ตํ•ด ๋‚˜ํƒ€๋‚ด๋Š” ๊ฒƒ๋„ ๊ฐ€๋Šฅํ•˜๋‹ค.

11111 -> 10์ง„์ˆ˜ ๋ณ€ํ™˜ -> 31

์ด๋กœ์จ, ํ•ด๋‹น ๋ถ€๋ถ„์ง‘ํ•ฉ์— i ๋ฅผ ์ถ”๊ฐ€ํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด i ๋ฒˆ์งธ ๋น„ํŠธ๋ฅผ 1๋กœ ๋ฐ”๊ฟ”์ฃผ์–ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด๋•Œ ๋น„ํŠธ ์—ฐ์‚ฐ์„ ์‚ฌ์šฉํ•œ๋‹ค.

๐Ÿชš ๋น„ํŠธ ์—ฐ์‚ฐ

  • AND(&) : ๋Œ€์‘ํ•˜๋Š” ๋‘ ๋น„ํŠธ๊ฐ€ ๋ชจ๋‘ 1์ผ๋•Œ๋งŒ 1์„ ๋ฐ˜ํ™˜
  • OR(|) : ๋Œ€์‘ํ•˜๋Š” ๋‘ ๋น„ํŠธ ์ค‘ ํ•˜๋‚˜๋ผ๋„ 1์ผ๋•Œ 1์„ ๋ฐ˜ํ™˜
  • XOR(^) : ๋Œ€์‘ํ•˜๋Š” ๋‘ ๋น„ํŠธ๊ฐ€ ์„œ๋กœ ๋‹ค๋ฅผ ๋•Œ๋งŒ 1์„ ๋ฐ˜ํ™˜
  • NOT(~) : ๋น„ํŠธ ๊ฐ’์„ ๋ฐ˜์ „ํ•˜์—ฌ ๋ฐ˜ํ™˜
  • SHIFT(>>, <<) : ์™ผ์ชฝ ํ˜น์€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋น„ํŠธ๋ฅผ ์˜ฎ๊ฒจ ๋ฐ˜ํ™˜

    • ์™ผ์ชฝ SHIFT (A << B) : A * 2^B
    • ์˜ค๋ฅธ์ชฝ SHIFT (A >> B) : A / 2^B
[์™ผ์ชฝ] 0001 โ†’ 0010 โ†’ 0100 โ†’ 1000 : 1 โ†’ 2 โ†’ 4 โ†’ 8 [์˜ค๋ฅธ์ชฝ] 1000 โ†’ 0100 โ†’ 0010 โ†’ 0001 : 8 โ†’ 4 โ†’ 2 โ†’ 1

๐Ÿชš ์˜ˆ์ œ๋ฅผ ํ†ตํ•œ ๊ตฌํ˜„

ํ”ผ์ž์ง‘์ด ์žˆ๋‹ค. ์—ฌ๊ธฐ์—๋Š” 0๋ถ€ํ„ฐ 19๊นŒ์ง€์˜ ๋ฒˆํ˜ธ๋ฅผ ๊ฐ–๋Š” ์Šค๋ฌด ๊ฐ€์ง€์˜ ํ† ํ•‘์ด ์žˆ๊ณ , ์ฃผ๋ฌธ ์‹œ ํ† ํ•‘์„ ๋„ฃ๊ฑฐ๋‚˜ ๋บ„ ์ˆ˜ ์žˆ๋‹ค.

  • ๊ทธ๋ ‡๋‹ค๋ฉด ํ•œ ํ”ผ์ž์˜ ์ •๋ณด๋Š” ์Šค๋ฌด ์ข…๋ฅ˜์˜ ์›์†Œ๋งŒ์„ ๊ฐ€์ง€๋Š” ์ง‘ํ•ฉ์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ์ด๋ฅผ boolean[] ์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜๋„ ์žˆ์ง€๋งŒ, ๋น„ํŠธ๋งˆ์Šคํ‚น์„ ์‚ฌ์šฉํ•œ๋‹ค.

๊ณต์ง‘ํ•ฉ๊ณผ ๊ฝ‰ ์ฐฌ ์ง‘ํ•ฉ

  • ํ† ํ•‘์„ ์˜ฌ๋ฆฌ์ง€ ์•Š์€ ํ”ผ์ž์™€ ๋ชจ๋“  ํ† ํ•‘์„ ์˜ฌ๋ฆฐ ํ”ผ์ž๋ฅผ ํ‘œํ˜„ํ•˜๋ ค๋ฉด ์•„๋ž˜์™€ ๊ฐ™์ด ํ•  ์ˆ˜ ์žˆ๋‹ค.
// ํ† ํ•‘์ด ์—†๋Š” ํ”ผ์ž int emptyPizza = 0; // ์Šค๋ฌด ๊ฐœ์˜ ํ† ํ•‘์„ ๋ชจ๋‘ ์˜ฌ๋ฆฐ ํ”ผ์ž int fullPizza = (1 << 20) - 1;
  • 1 << 20 ์€ 1๋’ค์— 20๊ฐœ์˜ 0์ด ์žˆ๋Š” ์ •์ˆ˜์ด๋ฏ€๋กœ, ์—ฌ๊ธฐ์„œ 1์„ ๋นผ๋ฉด 20๊ฐœ์˜ ๋น„ํŠธ๊ฐ€ ๋ชจ๋‘ ์ผœ์ง„ ์ •์ˆ˜๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ๋‹ค.

์›์†Œ ์ถ”๊ฐ€

  • ์ง‘ํ•ฉ์˜ ๊ฐ€์žฅ ๊ธฐ๋ณธ์ ์ธ ์—ฐ์‚ฐ์€ ์›์†Œ๋ฅผ ์ถ”๊ฐ€ํ•˜๊ณ  ์‚ญ์ œํ•˜๋Š” ๊ฒƒ์ด๋‹ค.
  • ๋น„ํŠธ๋งˆ์Šคํฌ๋ฅผ ์‚ฌ์šฉํ•œ ์ง‘ํ•ฉ์—์„œ ์›์†Œ๋ฅผ ์ถ”๊ฐ€ํ•œ๋‹ค๋Š” ๊ฒƒ์€ ํ•ด๋‹น ๋น„ํŠธ๋ฅผ ํ‚จ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค.
// ํ† ํ•‘ ๋ชฉ๋ก์— p๋ฒˆ ํ† ํ•‘์„ ์ถ”๊ฐ€ํ•˜๊ณ  ์‹ถ์€ ๊ฒฝ์šฐ toppings |= (1 << p);
  • 1 << p ๋Š” p๋ฒˆ์งธ ๋น„ํŠธ๋งŒ ์ผœ์ง„ ์ •์ˆ˜์ด๋‹ค.
  • ์ด๋ฏธ toppings ์— p๋ฒˆ ํ† ํ•‘์ด ์ถ”๊ฐ€๋œ ๊ฒฝ์šฐ ๊ฐ’์€ ๋ณ€ํ•˜์ง€ ์•Š๋Š”๋‹ค.

์›์†Œ ์‚ญ์ œ

// ํ† ํ•‘ ๋ชฉ๋ก์—์„œ p๋ฒˆ ํ† ํ•‘์„ ์‚ญ์ œํ•˜๊ณ  ์‹ถ์€ ๊ฒฝ์šฐ (ํ† ํ•‘ ๋ชฉ๋ก์— p๋ฒˆ ํ† ํ•‘์ด ์žˆ์–ด์•ผ ํ•จ) toppings -= (1 << p); // ํ† ํ•‘์ด ์—†์„ ๋•Œ๋„ ์ •์ƒ์ ์œผ๋กœ ๋™์ž‘ํ•˜๋Š” ์‚ญ์ œ toppings &= ~(1 << p);

์›์†Œ ํฌํ•จ ์—ฌ๋ถ€ ํ™•์ธ

  • ํ† ํ•‘ ๋ชฉ๋ก์— ์›ํ•˜๋Š” ํ† ํ•‘์ด ์ž˜ ์ถ”๊ฐ€๋˜์—ˆ๋Š”์ง€ ํ™•์ธํ•œ๋‹ค.
if ((toppings & (1 << p)) == (1 << p)) System.out.println("Topping is in!");
  • & ์—ฐ์‚ฐ์˜ ๊ฒฐ๊ณผ๊ฐ’์€ 0 ๋˜๋Š” 1 << p ์ด๋‹ค.

์›์†Œ์˜ ํ† ๊ธ€

  • ํ•ด๋‹น ๋น„ํŠธ๊ฐ€ ์ผœ์ ธ ์žˆ์œผ๋ฉด ๋„๊ณ , ๊บผ์ ธ ์žˆ๋‹ค๋ฉด ํ‚จ๋‹ค.
  • XOR ์—ฐ์‚ฐ์„ ์‚ฌ์šฉํ•œ๋‹ค.
toppings ^= (1 << p);

์ง‘ํ•ฉ์˜ ํฌ๊ธฐ ๊ตฌํ•˜๊ธฐ

  • ๊ฐ€์žฅ ๊ฐ„๋‹จํ•œ ๋ฐฉ๋ฒ•์€ ๊ฐ ๋น„ํŠธ๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ์ผœ์ ธ ์žˆ๋Š” ๋น„ํŠธ์˜ ์ˆ˜๋ฅผ ์ง์ ‘ ์„ธ๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.
  • ํ•˜์ง€๋งŒ JAVA์—์„œ๋Š” ์ด์™€ ๊ด€๋ จ๋œ ๋‚ด์žฅ ๋ช…๋ น์–ด๋ฅผ ์ œ๊ณตํ•œ๋‹ค.
System.out.println(Integer.bitCount(toppings));

์ตœ์†Œ ์›์†Œ ์ง€์šฐ๊ธฐ

  • ์ตœ์†Œ ์›์†Œ๊ฐ€ ๋ฌด์—‡์ธ์ง€ ์ƒ๊ด€์—†์ด ์ง€์šฐ๋Š” ์—ฐ์‚ฐ์ด ํ•„์š”ํ•  ๋•Œ ์œ ์šฉํ•˜๋‹ค.
toppings &= (toppings - 1);

toppings - 1 ์˜ ์ด์ง„์ˆ˜ ํ‘œํ˜„์„ ์ƒ๊ฐํ•ด๋ณด๋ฉด, ์ด๋Š” toppings ์—์„œ ์ผœ์ ธ ์žˆ๋Š” ์ตœํ•˜์œ„ ๋น„ํŠธ๋ฅผ ๋„๊ณ , ๊ทธ ๋ฐ‘์˜ ๋น„ํŠธ๋“ค์„ ์ „๋ถ€ ํ‚จ ์ปท์ด๋‹ค.

  • ๋”ฐ๋ผ์„œ ๋‘ ๊ฐ’์„ AND ์—ฐ์‚ฐํ•˜๋ฉด ์ตœํ•˜์œ„ ๋น„ํŠธ์™€ ๊ทธ ์ดํ•˜์˜ ๋น„ํŠธ๋“ค์€ ์ „๋ถ€ 0์ด ๋œ๋‹ค.
  • 40(10 1000)๊ณผ 39(10 0111)์„ AND ์—ฐ์‚ฐํ•˜๋ฉด 32(10 0000)๋กœ ์ตœํ•˜์œ„ ๋น„ํŠธ๊ฐ€ ๊บผ์ง„ ๊ฒƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.

๋ชจ๋“  ๋ถ€๋ถ„ ์ง‘ํ•ฉ ์ˆœํšŒ

  • ์ฃผ์–ด์ง„ ์ง‘ํ•ฉ์˜ ๋ชจ๋“  ๋ถ€๋ถ„ ์ง‘ํ•ฉ์„ ์ˆœํšŒํ•  ๊ฒฝ์šฐ๋„ ์œ ์šฉํ•˜๋‹ค.
for (int subset = pizza; subset; subset = ((subset - 1) & pizza)) { // subset์€ pizza์˜ ๋ถ€๋ถ„ ์ง‘ํ•ฉ }
  • (subset - 1) & pizza ์—์„œ, subset - 1 ๋กœ ์ผœ์ ธ ์žˆ๋˜ ์ตœํ•˜์œ„ ๋น„ํŠธ๊ฐ€ ๊บผ์ง€๊ณ , ๊ทธ ๋ฐ‘์˜ ๋น„ํŠธ๋“ค์€ ์ „๋ถ€ ์ผœ์ง€๊ฒŒ ๋œ๋‹ค. ์ด ๊ฒฐ๊ณผ์™€ pizza ์˜ ๊ต์ง‘ํ•ฉ์„ ๊ตฌํ•˜๋ฉด ๊ทธ ์ค‘ pizza ์— ์†ํ•˜์ง€ ์•Š๋Š” ๋น„ํŠธ๋“ค์€ ๋ชจ๋‘ ๊บผ์ง€๊ฒŒ ๋œ๋‹ค.
  • ์ด ์—ฐ์‚ฐ์„ ๋ฐ˜๋ณตํ•˜์—ฌ ๋ชจ๋“  ๋ถ€๋ถ„ ์ง‘ํ•ฉ์„ ์ˆœํšŒํ•  ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ subset = 0 ์ธ ์‹œ์ ์— ์ข…๋ฃŒ๋˜๊ธฐ์— ๊ณต์ง‘ํ•ฉ์€ ์ˆœํšŒํ•˜์ง€ ์•Š๋Š”๋‹ค.

๐Ÿ“• ์ฐธ๊ณ 

  • Tech Interview for developer
  • [ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ์—์„œ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ•ด๊ฒฐ ์ „๋žต] ๊ตฌ์ข…๋งŒ
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€